<!DOCTYPE html><html><head>
<title>page_util_norm_peg - Parser generator tools</title>
<style type="text/css"><!--
    HTML {
	background: 	#FFFFFF;
	color: 		black;
    }
    BODY {
	background: 	#FFFFFF;
	color:	 	black;
    }
    DIV.doctools {
	margin-left:	10%;
	margin-right:	10%;
    }
    DIV.doctools H1,DIV.doctools H2 {
	margin-left:	-5%;
    }
    H1, H2, H3, H4 {
	margin-top: 	1em;
	font-family:	sans-serif;
	font-size:	large;
	color:		#005A9C;
	background: 	transparent;
	text-align:		left;
    }
    H1.doctools_title {
	text-align: center;
    }
    UL,OL {
	margin-right: 0em;
	margin-top: 3pt;
	margin-bottom: 3pt;
    }
    UL LI {
	list-style: disc;
    }
    OL LI {
	list-style: decimal;
    }
    DT {
	padding-top: 	1ex;
    }
    UL.doctools_toc,UL.doctools_toc UL, UL.doctools_toc UL UL {
	font:		normal 12pt/14pt sans-serif;
	list-style:	none;
    }
    LI.doctools_section, LI.doctools_subsection {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding: 	0em;
    }
    PRE {
	display: 	block;
	font-family:	monospace;
	white-space:	pre;
	margin:		0%;
	padding-top:	0.5ex;
	padding-bottom:	0.5ex;
	padding-left:	1ex;
	padding-right:	1ex;
	width:		100%;
    }
    PRE.doctools_example {
	color: 		black;
	background: 	#f5dcb3;
	border:		1px solid black;
    }
    UL.doctools_requirements LI, UL.doctools_syntax LI {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding:	0em;
    }
    DIV.doctools_synopsis {
	color: 		black;
	background: 	#80ffff;
	border:		1px solid black;
	font-family:	serif;
	margin-top: 	1em;
	margin-bottom: 	1em;
    }
    UL.doctools_syntax {
	margin-top: 	1em;
	border-top:	1px solid black;
    }
    UL.doctools_requirements {
	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<!-- Generated from file 'page_util_norm_peg.man' by tcllib/doctools with format 'html'
   -->
<!-- Copyright &amp;copy; 2007 Andreas Kupries &amp;lt;andreas_kupries@users.sourceforge.net&amp;gt;
   -->
<!-- page_util_norm_peg.n
   -->
<body><hr> [
   <a href="../../../../../../../../home">Tcllib Home</a>
&#124; <a href="../../../../toc.html">Main Table Of Contents</a>
&#124; <a href="../../../toc.html">Table Of Contents</a>
&#124; <a href="../../../../index.html">Keyword Index</a>
&#124; <a href="../../../../toc0.html">Categories</a>
&#124; <a href="../../../../toc1.html">Modules</a>
&#124; <a href="../../../../toc2.html">Applications</a>
 ] <hr>
<div class="doctools">
<h1 class="doctools_title">page_util_norm_peg(n) 1.0 tcllib &quot;Parser generator tools&quot;</h1>
<div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
<p>page_util_norm_peg - page AST normalization, PEG</p>
</div>
<div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="doctools_toc">
<li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
<li class="doctools_section"><a href="#synopsis">Synopsis</a></li>
<li class="doctools_section"><a href="#section1">Description</a></li>
<li class="doctools_section"><a href="#section2">API</a></li>
<li class="doctools_section"><a href="#section3">Bugs, Ideas, Feedback</a></li>
<li class="doctools_section"><a href="#keywords">Keywords</a></li>
<li class="doctools_section"><a href="#category">Category</a></li>
<li class="doctools_section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="doctools_section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="doctools_synopsis">
<ul class="doctools_requirements">
<li>package require <b class="pkgname">page::util::norm_peg <span class="opt">?0.1?</span></b></li>
<li>package require <b class="pkgname">snit</b></li>
</ul>
<ul class="doctools_syntax">
<li><a href="#1"><b class="cmd">::page::util::norm::peg</b> <i class="arg">tree</i></a></li>
</ul>
</div>
</div>
<div id="section1" class="doctools_section"><h2><a name="section1">Description</a></h2>
<p>This package provides a single utility command which takes an AST for a
parsing expression grammar and normalizes it in various ways. The result
is called a <i class="term">Normalized PE Grammar Tree</i>.</p>
<p><em>Note</em> that this package can only be used from within a plugin
managed by the package <b class="package">page::pluginmgr</b>.</p>
</div>
<div id="section2" class="doctools_section"><h2><a name="section2">API</a></h2>
<dl class="doctools_definitions">
<dt><a name="1"><b class="cmd">::page::util::norm::peg</b> <i class="arg">tree</i></a></dt>
<dd><p>This command assumes the <i class="arg">tree</i> object contains for a
parsing expression grammar. It normalizes this tree in place.
The result is called a  <i class="term">Normalized PE Grammar Tree</i>.</p>
<p>The following operations are performd</p>
<ol class="doctools_enumerated">
<li><p>The data for all terminals is stored in their grandparental
nodes. The terminal nodes and their parents are removed. Type
information is dropped.</p></li>
<li><p>All nodes which have exactly one child are irrelevant and are
removed, with the exception of the root node. The immediate
child of the root is irrelevant as well, and removed as well.</p></li>
<li><p>The name of the grammar is moved from the tree node it is stored
in to an attribute of the root node, and the tree node removed.</p>
<p>The node keeping the start expression separate is removed as
irrelevant and the root node of the start expression tagged with
a marker attribute, and its handle saved in an attribute of the
root node for quick access.</p></li>
<li><p>Nonterminal hint information is moved from nodes into attributes,
and the now irrelevant nodes are deleted.</p>
<p><em>Note:</em> This transformation is dependent on the removal of all
nodes with exactly one child, as it removes the all 'Attribute'
nodes already. Otherwise this transformation would have to put
the information into the grandparental node.</p>
<p>The default mode given to the nonterminals is <b class="const">value</b>.</p>
<p>Like with the global metadata definition specific information
is moved out out of nodes into attributes, the now irrelevant
nodes are deleted, and the root nodes of all definitions are
tagged with marker attributes. This provides us with a mapping
from nonterminal names to their defining nodes as well, which
is saved in an attribute of the root node for quick reference.</p>
<p>At last the range in the input covered by a definition is
computed. The left extent comes from the terminal for the
nonterminal symbol it defines. The right extent comes from
the rightmost child under the definition. While this not an
expression tree yet the location data is sound already.</p></li>
<li><p>The remaining nodes under all definitions are transformed
into proper expression trees. First character ranges, followed
by unary operations, characters, and nonterminals. At last the
tree is flattened by the removal of superfluous inner nodes.</p>
<p>The order matters, to shed as much nodes as possible early, and
to avoid unnecessary work later.</p></li>
</ol></dd>
</dl>
</div>
<div id="section3" class="doctools_section"><h2><a name="section3">Bugs, Ideas, Feedback</a></h2>
<p>This document, and the package it describes, will undoubtedly contain
bugs and other problems.
Please report such in the category <em>page</em> of the
<a href="http://core.tcl.tk/tcllib/reportlist">Tcllib Trackers</a>.
Please also report any ideas for enhancements you may have for either
package and/or documentation.</p>
<p>When proposing code changes, please provide <em>unified diffs</em>,
i.e the output of <b class="const">diff -u</b>.</p>
<p>Note further that <em>attachments</em> are strongly preferred over
inlined patches. Attachments can be made by going to the <b class="const">Edit</b>
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar.</p>
</div>
<div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
<p><a href="../../../../index.html#peg">PEG</a>, <a href="../../../../index.html#graph_walking">graph walking</a>, <a href="../../../../index.html#normalization">normalization</a>, <a href="../../../../index.html#page">page</a>, <a href="../../../../index.html#parser_generator">parser generator</a>, <a href="../../../../index.html#text_processing">text processing</a>, <a href="../../../../index.html#tree_walking">tree walking</a></p>
</div>
<div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
<p>Page Parser Generator</p>
</div>
<div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2007 Andreas Kupries &lt;andreas_kupries@users.sourceforge.net&gt;</p>
</div>
</div></body></html>
